package com.itheima.leetcode.od.b.dynamicprogramming;

import java.util.ArrayList;
import java.util.stream.Collectors;

/**
 * (C卷,200分)- 伐木工（Java & JS & Python & C & C++）
 * <p>
 * 题目描述
 * <p>
 * 一根X米长的树木，伐木工切割成不同长度的木材后进行交易，交易价格为每根木头长度的乘积。规定切割后的每根木头长度都为正整数；也可以不切割，直接拿整根树木进行交易。
 * <p>
 * 请问伐木工如何尽量少的切割，才能使收益最大化？
 * <p>
 * 输入描述
 * <p>
 * 木材的长度（X ≤ 50）
 * <p>
 * 输出描述
 * <p>
 * 输出最优收益时的各个树木长度，以空格分隔，按升序排列
 * <p>
 * 用例
 * <p>
 * 输入	10
 * 输出	3 3 4
 * 说明
 * 一根2米长的树木，伐木工不切割，为2 * 1，收益最大为2
 * <p>
 * 一根4米长的树木，伐木工不需要切割为2 * 2，省去切割成本，直接整根树木交易，为4 * 1，收益最大为4
 * <p>
 * 一根5米长的树木，伐木工切割为2 * 3，收益最大为6
 * <p>
 * 一根10米长的树木，伐木工可以切割方式一：3，4，3，也可以切割为方式二：3，2，2，3，但方式二伐木工多切割一次，增加切割成本却买了一样的价格，因此并不是最优收益。
 */
public class Loggers {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();*/

        int x = 10;

        System.out.println(getResult(x));
    }

    public static String getResult(int x) {
        Wood[] dp = new Wood[x + 1];

        for (int i = 0; i <= x; i++) {
            // 初始时，将木材不切割的收益作为最大收益
            dp[i] = new Wood();
            dp[i].profit = i;
            dp[i].slices.add(i);
        }

        // 从长度为2的木材开始尝试切割
        for (int i = 2; i <= x; i++) {
            for (int j = 1; j < i; j++) {
                int profit = dp[j].profit * dp[i - j].profit;

                // 如果该切割方案的收益更大，或者收益和之前切割方案的收益相同，但是切割数更少，则使用当前切割方案
                if (profit > dp[i].profit
                        || (profit == dp[i].profit
                        && dp[i].slices.size() > (dp[j].slices.size() + dp[i - j].slices.size()))) {
                    dp[i].profit = profit;
                    dp[i].slices.clear();
                    dp[i].slices.addAll(dp[j].slices);
                    dp[i].slices.addAll(dp[i - j].slices);
                }
            }
        }

        // dp[x].slices记录的是：长度x的木材对应的最大收益的切割方案
        // 按题目输出描述要求进行升序
        dp[x].slices.sort((a, b) -> a - b);

        // 打印切割方案
        return dp[x].slices.stream()
                .map(String::valueOf)
                .collect(Collectors.joining(" "));
    }

    static class Wood {
        int profit; // 记录木材的最大收益
        ArrayList<Integer> slices = new ArrayList<>(); // 记录木材最大收益时对应的切割状态
    }
}